package cn.edu.xjtu.data_structure.chapter01_linearlist.question;

import cn.edu.xjtu.data_structure.chapter01_linearlist.sqlist.SequentialList;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/9/10 16:24
 */
public class FindAndInsert {
    /**
     * 已知一个顺序表List，其中的元素递增有序排列，设计一个算法，
     * 插入一个元素x（x为int型）后该顺序表仍然保持递增有序排列
     * （假设插入总是有效）
     */
    int findElement(SequentialList<Integer> list, int x) {
        int i;
        for(i=0;i<list.length();i++){
            list.next();//当前元素向后移
            if (x<list.currValue()){
                return i;//从小到大逐个判断
            }
        }
        return i;//插入到表尾
    }

    void insertElement(SequentialList<Integer> list, int x){
        int pos = findElement(list,x);//找到插入的位置
        list.setPosition(pos);//将当前元素设置到插入的位置
        list.insert(x);
    }

    public static void main(String[] args) {
        SequentialList<Integer>sequentialList = new SequentialList<>();
        sequentialList.insert(6);
        sequentialList.insert(5);
        sequentialList.insert(4);
        sequentialList.insert(3);
        sequentialList.insert(2);
        sequentialList.insert(1);
        FindAndInsert test = new FindAndInsert();
        test.insertElement(sequentialList,4);
        sequentialList.print();
    }

}
